--region AstarManager1.lua
--Author : east
--Date   : 2016/05/11
--generate by [generate_ui_code.py] automatically

local AstarManager  = {}

local tableRemove = table.remove;
local mathAbs = math.abs;
local mathPow = math.pow;


local function getTwoGLen(indexX1, indexY1, indexX2, indexY2)
    local numX = mathAbs(indexX1 - indexX2);
    local numY = mathAbs(indexY1 - indexY2);
    local diff = mathAbs(numX-numY);
    local tempMin = numX > numY and numY or numX;
    return (mathPow(2, 2)*tempMin + diff);
end

local function checkIsInList(list, block)
    for i, v in ipairs(list) do
        if v == block then
            return true;
        end
    end
    return false;
end


----data from 0 to max-1
function AstarManager:search(data, width, height, startPos, endPos)
    -- endPos.x = 19;
    -- endPos.y = 19;
    print("curPos:", startPos.x, startPos.y);
    print("endPos:", endPos.x, endPos.y, data[endPos.y][endPos.x]);

    if startPos.x == endPos.x and startPos.y == endPos.y then
        return {endPos}
    end

    -- print("first:", data[startPos.y][startPos.x-1])
    -- print("first:", data[startPos.y-1][startPos.x])
    -- print("first:", data[startPos.y-1][startPos.x-1])
    -- print("first:", startPos.y, startPos.x+1, data[startPos.y][startPos.x+1])
    -- print("first:", data[startPos.y+1][startPos.x])
    -- print("first:", data[startPos.y+1][startPos.x+1])
    
    local isCouldPass = false;
    local findPath = {};

    if data == nil or data[0] == nil or data[0][0] == nil then
        -- print("return4=================")
        return findPath
    end

    -- local time0 = os.clock();
    ------from 0...
    local maxW = #data[0] + 1;
    local maxH = #data + 1;
    -- print("maxW, maxH", maxW, maxH);
    local blocks = {};
    if self._blocks then
        blocks = self._blocks;
    else
        local tempIsPath = false;
        
        for row = 0, maxH-1 do
            if blocks[row] == nil then
                blocks[row] = {};
            end
            for col = 0,maxW-1 do
                tempIsPath = false;
                if data[row][col] == 0 then
                    tempIsPath = true;
                end
                -----------------this cost some times
                blocks[row][col] = {isPath = tempIsPath, G = 0, H = 0, indexX = col, indexY = row, parent = nil, getF = function(self) return (self.G+self.H) end};
                -- if row == 30 and col == 41 then
                --     print("fuck:", blocks[row][col].isPath);
                --     dump(blocks[row][col])
                --     print("test:", tempIsPath);
                -- end
            end
        end
        -------------------缓存一下，多地图就要修改了===============
        self._blocks = blocks;
    end
    
    -- print("okokok")
    -- dump(blocks);
    -- local time00 = os.clock();
    -- print("time cost00-0:", time00 - time0);

    local curIndexX = startPos.x;
    local curIndexY = startPos.y;
    local posIndexX = endPos.x;
    local posIndexY = endPos.y;
    local curBlock = blocks[curIndexY][curIndexX];
    local posBlock = blocks[posIndexY][posIndexX];


    local totalPathCount = 0;
    for row = 0, maxH-1 do
        for col = 0, maxW-1 do
            local tempBlock = blocks[row][col];
            if(tempBlock.isPath == true) then
                local numX = mathAbs(col-posIndexX);
                local numY = mathAbs(row-posIndexY);
                tempBlock.H = numX + numY;
            
                tempBlock.G = getTwoGLen(col, row, curIndexX, curIndexY);
                tempBlock.parent = nil;
                totalPathCount = totalPathCount + 1;
            end
            

        end
    end

    -- if posBlock.isPath == false then-----是障碍物，找到最近的可以走到的位置
        

    --     local nearBlockDiff = 1;
    --     local detectDirX = curIndexX - posIndexX;
    --     local detectDirY = curIndexY - posIndexY;
    --     if detectDirX < 0 then
    --         detectDirX = -1;
    --     elseif detectDirX > 0 then
    --         detectDirX = 1;
    --     end
    --     if detectDirY < 0 then
    --         detectDirY = -1;
    --     elseif detectDirY > 0 then
    --         detectDirY = 1;
    --     end

    --     while true do
    --         local tempBlock = nil;
    --         local tempIndexX = posIndexX + nearBlockDiff*detectDirX;
    --         local tempIndexY = posIndexY + nearBlockDiff*detectDirY;
    --         if tempIndexY < maxH and tempIndexY >= 0 then
    --             tempBlock = blocks[tempIndexY][posIndexX];
    --             if tempBlock.isPath == true then
    --                 nearBlock = tempBlock;
    --                 break;
    --             end
    --         end
            
    --         if tempIndexX < maxW and tempIndexX >= 0 then
    --             tempBlock = blocks[posIndexY][tempIndexX];
    --             if tempBlock.isPath == true then
    --                 nearBlock = tempBlock;
    --                 break;
    --             end
    --         end
            
    --         nearBlockDiff = nearBlockDiff + 1;
    --     end
    --     if nearBlock == nil then
            -- print("return1=================")
    --         return self.findPath;
    --     else
    --         posIndexX = nearBlock.indexX;
    --         posIndexY = nearBlock.indexY;
    --         posBlock = nearBlock;
    --         print("there is new endPos:", posBlock.indexX, posBlock.indexY, posBlock.isPath);
    --     end

    -- end


    local openList = {curBlock};
    local closeList = {};

    local isFindPosBlock = false;

    -- local time1 = os.clock();
    -- print("time cost1-00:", time1 - time00);
    while true do
        local tempOpenLen = #openList;
        if 0 >= tempOpenLen then
            log.debug("can not find path");
            break;
        end

        local tempMinOpenBlock = nil;
        local tempIt1 = 1;

        for it1 = 1, tempOpenLen do
            local tempOpenBlock = openList[it1];
            if not tempMinOpenBlock then
                tempMinOpenBlock = tempOpenBlock;
                tempIt1 = 1;
            elseif tempMinOpenBlock:getF() > tempOpenBlock:getF() then
                tempMinOpenBlock = tempOpenBlock;
                tempIt1 = it1;
            end
        end
        -- print("tempMinOpenBlock=============", tempMinOpenBlock, tempIt1);
        closeList[#closeList+1] = tempMinOpenBlock;
        tableRemove(openList, tempIt1);

        if tempMinOpenBlock == posBlock then
            isFindPosBlock = true;
            log.debug("find the target");
            break;
        end

        -- local time2 = os.clock();
        -- print("time cost2-1:", time2 - time1);
        ----------------------find the min F
        -- print("begin=======================")
        -- print(tempMinOpenBlock.indexX, tempMinOpenBlock.indexY);
        -- dump(blocks);

        local tempBlock1;
        if tempMinOpenBlock.indexX > 0 then
            tempBlock1 = blocks[tempMinOpenBlock.indexY][tempMinOpenBlock.indexX-1];
            if not checkIsInList(openList, tempBlock1) and not checkIsInList(closeList, tempBlock1) and tempBlock1.isPath then
                -- print("haha===============1")
                tempBlock1.parent = tempMinOpenBlock;
                openList[#openList + 1] = tempBlock1;
            end
        end

        if tempMinOpenBlock.indexX < maxW-1 then
            tempBlock1 = blocks[tempMinOpenBlock.indexY][tempMinOpenBlock.indexX+1];
            
            if not checkIsInList(openList, tempBlock1) and not checkIsInList(closeList, tempBlock1) and tempBlock1.isPath then
                -- print("haha===============2")
                tempBlock1.parent = tempMinOpenBlock;
                openList[#openList + 1] = tempBlock1;
            end
        end
        if tempMinOpenBlock.indexY > 0 then
            tempBlock1 = blocks[tempMinOpenBlock.indexY-1][tempMinOpenBlock.indexX];
            if not checkIsInList(openList, tempBlock1) and not checkIsInList(closeList, tempBlock1) and tempBlock1.isPath then
                -- print("haha===============3")
                tempBlock1.parent = tempMinOpenBlock;
                openList[#openList + 1] = tempBlock1;
            end
        end
        if tempMinOpenBlock.indexY < maxH-1 then
            tempBlock1 = blocks[tempMinOpenBlock.indexY+1][tempMinOpenBlock.indexX];
            if not checkIsInList(openList, tempBlock1) and not checkIsInList(closeList, tempBlock1) and tempBlock1.isPath then
                -- print("haha===============4")
                tempBlock1.parent = tempMinOpenBlock;
                openList[#openList + 1] = tempBlock1;
            end
        end

        if tempMinOpenBlock.indexX > 0 and tempMinOpenBlock.indexY > 0 and (isCouldPass or (blocks[tempMinOpenBlock.indexY][tempMinOpenBlock.indexX - 1].isPath and blocks[tempMinOpenBlock.indexY - 1][tempMinOpenBlock.indexX].isPath)) then
            tempBlock1 = blocks[tempMinOpenBlock.indexY-1][tempMinOpenBlock.indexX-1];
            if not checkIsInList(openList, tempBlock1) and not checkIsInList(closeList, tempBlock1) and tempBlock1.isPath then
                -- print("haha===============5")
                tempBlock1.parent = tempMinOpenBlock;
                openList[#openList + 1] = tempBlock1;
            end
        end
        if tempMinOpenBlock.indexX > 0 and tempMinOpenBlock.indexY < maxH-1 and (isCouldPass or (blocks[tempMinOpenBlock.indexY][tempMinOpenBlock.indexX - 1].isPath and blocks[tempMinOpenBlock.indexY + 1][tempMinOpenBlock.indexX].isPath)) then
            tempBlock1 = blocks[tempMinOpenBlock.indexY+1][tempMinOpenBlock.indexX-1];
            if not checkIsInList(openList, tempBlock1) and not checkIsInList(closeList, tempBlock1) and tempBlock1.isPath then
                -- print("haha===============6")
                tempBlock1.parent = tempMinOpenBlock;
                openList[#openList + 1] = tempBlock1;
            end
        end
        if tempMinOpenBlock.indexX < maxW-1 and tempMinOpenBlock.indexY < maxH-1 and (isCouldPass or (blocks[tempMinOpenBlock.indexY][tempMinOpenBlock.indexX + 1].isPath and blocks[tempMinOpenBlock.indexY + 1][tempMinOpenBlock.indexX].isPath)) then
            tempBlock1 = blocks[tempMinOpenBlock.indexY+1][tempMinOpenBlock.indexX+1];
            if not checkIsInList(openList, tempBlock1) and not checkIsInList(closeList, tempBlock1) and tempBlock1.isPath then
                -- print("haha===============7")
                tempBlock1.parent = tempMinOpenBlock;
                openList[#openList + 1] = tempBlock1;
            end
        end
        if tempMinOpenBlock.indexX < maxW-1 and tempMinOpenBlock.indexY > 0 and (isCouldPass or (blocks[tempMinOpenBlock.indexY][tempMinOpenBlock.indexX + 1].isPath and blocks[tempMinOpenBlock.indexY - 1][tempMinOpenBlock.indexX].isPath)) then
            tempBlock1 = blocks[tempMinOpenBlock.indexY-1][tempMinOpenBlock.indexX+1];
            if not checkIsInList(openList, tempBlock1) and not checkIsInList(closeList, tempBlock1) and tempBlock1.isPath then
                -- print("haha===============8")
                tempBlock1.parent = tempMinOpenBlock;
                openList[#openList + 1] = tempBlock1;
            end
        end
        -- local time3 = os.clock();
        -- print("time cost2-1:", time3 - time2);


    end
    -- print("findPath cost time:", os.clock() - time1);


    local tempBlock = posBlock;
    if isFindPosBlock == false then
        -- print("return2=================")
        -- dump(closeList);
        -- print("不应该啊=")
        local tempMinH = nil;
        for i, v in pairs(closeList) do
            if tempMinH == nil then
                tempMinH = v.H;
                tempBlock = v;
            elseif tempMinH > v.H then
                tempMinH = v.H;
                tempBlock = v;
            end            
        end
        -- return findPath;
    end

    log.debug("tempBlock.indexX:%d  tempBlock.indexY:%d", tempBlock.indexX, tempBlock.indexY);
    local isHadPrintAll = false;

    local tempAry1 = {};

    while (true) do
        for it2 = 1, #closeList do
            local tempCloseBlock = closeList[it2];
            if tempBlock == tempCloseBlock then
                tempBlock = tempCloseBlock.parent;
                tableRemove(closeList, it2);
                -- log.debug("tempBlock.indexX:%d  tempBlock.indexY:%d", tempBlock.indexX, tempBlock.indexY);
                tempAry1[#tempAry1+1] = {x = tempBlock.indexX, y = tempBlock.indexY};
                if tempBlock == curBlock then
                    isHadPrintAll = true;
                end
                break;
            end
            
        end
        if isHadPrintAll then
            break;
        end
    end

    local tempLen = #tempAry1;
    local findIt = 2;
    if tempLen == 1 then
        findIt = 1;
    end
    for i = findIt, tempLen do------去掉当前各格子，不然会抖一下。如果只有一步就不去掉
        findPath[i-findIt+1] = tempAry1[tempLen-i+1];
    end
    -- print("return3=================")
    -- print("last:");
    -- dump(findPath);
    return findPath;


end


return AstarManager






